#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

// 两数之和
class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        // 存 <nums[i],i>
        unordered_map<int, int> hash;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            int num = target - nums[i];
            if (hash.count(num))
            {
                return {hash[num], i};
            }
            hash[nums[i]] = i;
        }

        return {-1, -1};
    }
};

// 字母异位词分组
class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs)
    {
        unordered_map<string, vector<string>> hash;
        // 1.字母异位词分组
        for (auto &str : strs)
        {
            string tmp = str;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(str);
        }
        // 2.提取异位词
        vector<vector<string>> ans;
        for (auto &[x, y] : hash)
        {
            ans.push_back(y);
        }
        return ans;
    }
};

// 最长连续序列
class Solution
{
public:
    int longestConsecutive(vector<int> &nums)
    {
        unordered_set<int> hash;
        for (auto &x : nums)
        {
            hash.insert(x);
        }

        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            // 如果nums[i] - 1 存在,那么nums[i]不可能作为起始位置
            if (!hash.count(nums[i] - 1))
            {
                int count = 1;
                int num = nums[i];
                while (hash.count(num + 1))
                {
                    count++;
                    num++;
                }
                ans = max(count, ans);
            }
        }
        return ans;
    }
};

// 移动零
class Solution
{
public:
    void moveZeroes(vector<int> &nums)
    {
        int left = -1, right = 0, n = nums.size();
        // [0,left] 不为0 [left + 1,right] == 0
        while (right < n)
        {
            while (right < n && nums[right] == 0)
                right++;
            if (right < n)
                swap(nums[++left], nums[right++]);
        }
    }
};

// 盛最多水多容器
class Solution
{
public:
    int maxArea(vector<int> &height)
    {
        int n = height.size(), ans = 0;
        int left = 0, right = n - 1;
        // 不断向中间靠拢,两边高度低的移动
        while (left < right)
        {
            ans = max(ans, (right - left) * min(height[left], height[right]));
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ans;
    }
};

// 三数之和
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < n - 2;)
        {
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum == target)
                {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    // 去重
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
                else if (sum < target)
                    left++;
                else
                    right--;
            }
            i++;
            while (i < n - 2 && nums[i] == nums[i - 1])
                i++;
        }

        return ans;
    }
};

// 接雨水
class Solution
{
public:
    int trap(vector<int> &nums)
    {
        // 找到右边第一个比自己大的元素
        stack<int> st;
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            while (st.size() && nums[i] > nums[st.top()])
            {
                int top = st.top();
                st.pop();
                if (st.empty())
                {
                    break;
                }
                int left = st.top();
                int width = i - left - 1;
                int height = min(nums[left], nums[i]) - nums[top];
                ans += width * height;
            }
            st.push(i);
        }

        return ans;
    }
};